class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n-1;
        while (i >= 0 && i < m && j >= 0 && j < n){
            if (target > matrix[i][j]){
                i++;
            }else if(target < matrix[i][j]){
                j--;
            } else {
                return true;
            }
        }
        return false;
    }

    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int rowIndex = binarySearchFirstColumn(matrix, target);
            if (rowIndex < 0) {
                return false;
            }
            return binarySearchRow(matrix[rowIndex], target);
        }
    
        public int binarySearchFirstColumn(int[][] matrix, int target) {
            // 对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
            int low = -1, high = matrix.length - 1;
            while (low < high) {
                int mid = (high - low + 1) / 2 + low;
                if (matrix[mid][0] <= target) {
                    low = mid;
                } else {
                    high = mid - 1;
                }
            }
            return low;
        }
    
        public boolean binarySearchRow(int[] row, int target) {
            int low = 0, high = row.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (row[mid] == target) {
                    return true;
                } else if (row[mid] > target) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return false;
        }
    }
}